'''
难度 中等
题目链接 https://leetcode.cn/problems/merge-intervals/description/
'''

from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        结果 = []
        intervals.sort()
        开始 = intervals[0][0]
        结束 = intervals[0][1]
        for i in range(1, len(intervals)):
            # 当前的开始 比前一个的结束大 则不连续 需要分开
            if intervals[i][0] > 结束:
                结果.append([开始, 结束])
                开始 = intervals[i][0]
                结束 = intervals[i][1]
            else:
                结束 = max(intervals[i][1], 结束)
                
        # 最后一组还需要添加进去
        结果.append([开始, 结束])
        return 结果
    

if __name__ == '__main__':
    s = Solution()
    参数 = [
        [[[1,3],[2,6],[8,10],[15,18]]],
        [[[1,4],[4,5]]],
    ]
    预期 = [
        [[1,6],[8,10],[15,18]],
        [[1,5]],
    ]
    for k,v in enumerate(参数):
        r = s.merge(v[0])
        if r != 预期[k]:
            print("第{}个case不通过 期望={} 结果={}\n".format(
                k+1,
                预期[k],
                r
            ))